Trinomial

Memory limit: 32 MB

Consider a trinomial . We are interested in the coefficients of the expansion of this trinomial:

For example, .

Task

Write a program which:

• reads from the standard input sets of data that comprise numbers and ,
• for each set of data computes modulo , where is the coefficient of in the expansion of the trinomial ,
• for each set of data writes the computed number to the standard output.

Input

In the first line of the standard input there is one integer denoting the number of the data sets, . It is followed by sets of data, one per line. Each set consists of two non-negative integers and separated by a single space, , .

Output

One should write lines to the standard output. The -th line ought to contain one non-negative integer being modulo for the numbers from the -th set.

Example

For the input data:

5
2 0
7 4
4 5
5 3
8 15

the correct result is:

1
2
1
0
2

Task author: Krzysztof Sikora.